#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <queue>
#include <stack>
#include <vector>
#define MAX_SIZE 101

using namespace std;

int main()
{
    int N, M, v1, v2, cost, tv1, tv2, num_task = 0;
    int finalc[MAX_SIZE]={0}, judgec[MAX_SIZE]={0};
    int costmap[MAX_SIZE][MAX_SIZE];
    int indegree[MAX_SIZE] = {0};
    vector<int> connect[MAX_SIZE];
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &v1, &v2, &cost);
        indegree[v2]++;
        costmap[v1][v2] = costmap[v2][v1] = cost;
        connect[v1].push_back(v2);
    }

    queue<int> myqueue;
    stack<int> mystack;
    // 开始进入出入度的队列入队
    for (int i = 1; i <= N; i++)
        if (indegree[i] == 0)
            myqueue.push(i);

    // 循环并计算
    while(!myqueue.empty())
    {
        // 用来看是否所有任务都可以达到
        num_task++;
        tv1 = myqueue.front();
        myqueue.pop();
        mystack.push(tv1);
        for (int i = 0; i < connect[tv1].size(); i++)
        {
            tv2 = connect[tv1][i];
            if (--indegree[tv2] == 0)
                myqueue.push(tv2);
            if (finalc[tv2] < finalc[tv1] + costmap[tv1][tv2])
                finalc[tv2] = finalc[tv1] + costmap[tv1][tv2];
        }
    }
    // 如果队列走完了数量不对 那就是有不连通的点
    if (num_task != N)
    {
        printf("0");
        return 0;
    }
    printf("%d\n", finalc[mystack.top()]);
    
    // init all judgec
    for (int i = 1; i <= N; i++)
        judgec[i] = finalc[mystack.top()];

    while(!mystack.empty())
    {
        tv1 = mystack.top();
        mystack.pop();

        for (int i = 0; i < connect[tv1].size(); i++)
        {
            tv2 = connect[tv1][i];
            if(judgec[tv1] > judgec[tv2] - costmap[tv1][tv2])
                judgec[tv1] = judgec[tv2] - costmap[tv1][tv2];
        }
    }

    // 编号小的开始
    for (int i = 1; i <= N; i++)
        for (int j = connect[i].size() - 1; j >= 0; j--)
        {
            tv2 = connect[i][j];
            // 判断是否有冗余时间，如果没有就是关键任务
            if (judgec[tv2] - finalc[i] - costmap[i][tv2] == 0)
                printf("%d->%d\n", i, tv2);
        }
    return 0;
}